/**
 * @ClassName Code02_DeleteGivenValue
 * @Description: TODO
 * @Author: JCC
 * @CreateTime: 2023/12/13 12:22
 */

import java.util.LinkedList;

/**
 * 删除指定结点
 */
public class Code02_DeleteGivenValue {

    // 结点
    static class Node {
        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    // 删除指定单链表
    public static Node deleteGivenValue(Node head, int value) {
        // 来到第一个不需要删的位置
        while (head != null && head.value == value) {
            head = head.next;
        }
        // head == null
        // head != null
        Node pre = head;
        Node cur = head;
        while (cur != null) {
            if (cur.value == value) {
                pre.next = cur.next;
            } else {
                pre = cur;
            }
            cur = cur.next;
        }
        return head;
    }

    // 随机生成单链表
    public static Node generateRandomLinkedList(int len, int value) {
        int size = (int) (Math.random() * (len + 1));
        if (size == 0) {
            return null;
        }
        Node head = new Node((int) (Math.random() * (value + 1)));
        Node pre = head;
        while (size - 1 != 0) {
            Node cur = new Node((int) (Math.random() * (value + 1)));
            pre.next = cur;
            pre = cur;
            size--;
        }
        return head;
    }

    // 打印单链表
    public static void printLinkedList(Node head) {
        while (head != null) {
            System.out.print(head.value + " ");
            head = head.next;
        }
        System.out.println();
    }

    // 测试删除指定单链表
    public static Node testDeleteGivenValue(Node head, int value) {
        LinkedList<Node> list = new LinkedList<>();
        while (head != null) {
            if (head.value != value) {
                list.add(head);
            }
            head = head.next;
        }
        int size = list.size();
        if (size == 0) {
            return null;
        }
        for (int i = 1; i < size; i++) {
            list.get(i - 1).next = list.get(i);
        }
        list.get(size - 1).next = null;
        return list.get(0);
    }

    // 判断是否删除了所有指定结点
    public static boolean isClearAllGivenNode(Node head, int value) {
        while (head != null) {
            if (head.value == value) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    // 复制单链表
    public static Node copyLinkedList(Node head) {
        LinkedList<Integer> list = new LinkedList<>();
        while (head != null) {
            list.add(head.value);
            head = head.next;
        }
        int size = list.size();
        if (size == 0) {
            return null;
        }
        Node newHead = new Node(list.get(0));
        Node pre = newHead;
        for (int i = 1; i < size; i++) {
            Node cur = new Node(list.get(i));
            pre.next = cur;
            pre = cur;
        }
        return newHead;
    }

    // 是否为相同单链表
    public static boolean isSameLinkedList(Node head, Node copy) {
        if (head == null && copy == null) {
            return true;
        }
        while (head != null && copy != null) {
            if (head.value != copy.value) {
                return false;
            }
            head = head.next;
            copy = copy.next;
        }
        if (copy == null && head == null) {
            return true;
        } else {
            return false;
        }
    }

    public static void main(String[] args) {
        int len = 10;
        int value = 100;
        int testTimes = 10000;
        System.out.println("测试开始");
        for (int i = 0; i < testTimes; i++) {
            Node head = generateRandomLinkedList(len, value);
            Node copyHead = copyLinkedList(head);
            int randDeleteValue = (int) (Math.random() * (value + 1));
            Node headClean = deleteGivenValue(head, randDeleteValue);
            Node copyHeadClean = testDeleteGivenValue(copyHead, randDeleteValue);
            boolean flag1 = isClearAllGivenNode(headClean, randDeleteValue);
            boolean flag2 = isClearAllGivenNode(copyHeadClean, randDeleteValue);
            if (!flag1 || !flag2) {
                System.out.println("测试异常");
                System.out.println("randDeleteValue：" + randDeleteValue);
                System.out.print("head：");
                printLinkedList(head);
                System.out.print("copyHead：");
                printLinkedList(copyHead);
                System.out.print("headClean：");
                printLinkedList(headClean);
                System.out.print("copyHeadClean：");
                printLinkedList(copyHeadClean);
                break;
            }
        }
        System.out.println("测试结束");
    }
}